package com.peng.leetcode.tree;

/**
 * CountNodes1
 * 222. 完全二叉树的节点个数
 * https://leetcode.cn/problems/count-complete-tree-nodes/
 * <p>
 * Created on 2022/12/2
 *
 * @author lupeng
 */
public class CountNodesByBinarySearch {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int lc = levelCount(root.left);
        int rc = levelCount(root.right);
        if (lc == rc) {
            return countNodes(root.right) + (1 << lc);
        } else {
            return countNodes(root.left) + (1 << rc);
        }
    }

    int levelCount(TreeNode r) {
        int ans = 0;
        while (r != null) {
            r = r.left;
            ans++;
        }
        return ans;
    }
}
